/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-abbreviation
   @Language: C++
   @Datetime: 19-04-23 17:53
   */


class Solution {
	int getnum(const string &str){
		int pos=0;
		for(pos=0; pos<str.length() && !isdigit(str[pos]); ++pos);
		return atoi(str.c_str()+pos);
	}
	bool duplicate(unordered_multimap<string,string> &abbrs, unordered_map<string,string> &words){
		bool found=false;
		char abbr[400];
		vector<pair<string,string> > vs;
		vector<string> del;
		for(auto it=abbrs.begin(); it!=abbrs.end();){
			if(abbrs.count(it->first)<2) {
				it++;
				continue;
			}
			found=true;
			del.push_back(it->first);
			for(auto range=abbrs.equal_range(it->first); range.first!=range.second; ++range.first){
				string word=range.first->second;
				int num=getnum(range.first->first);
				memset(abbr,0,400);
				strncpy(abbr,word.c_str(),word.length()-num);
				sprintf(abbr+strlen(abbr),"%d%c",num-1,word.back());
				if(strlen(abbr)>=word.length()) sprintf(abbr,"%s",word.c_str());
				vs.push_back(make_pair(abbr,word));
				words[word]=abbr;
				it++;
			}
		}
		for(const string &s:del)
			abbrs.erase(s);
		for(const auto &p:vs)
			abbrs.insert(p);
		return found;
	}
public:
	/**
	 * @param dict: an array of n distinct non-empty strings
	 * @return: an array of minimal possible abbreviations for every word
	 */
	vector<string> wordsAbbreviation(vector<string> &dict) {
		// write your code here
		unordered_multimap<string,string> abbrs;
		unordered_map<string,string> words;
		vector<string> vs(dict.size());
		char abbr[400];
		for(const string &word:dict){
			if(word.length()<4) sprintf(abbr,"%s",word.c_str());
			else sprintf(abbr,"%c%d%c",word[0],word.length()-2,word.back());
			abbrs.insert(make_pair(abbr,word));
			words[word]=abbr;
		}
		for(bool found=true; found; found=duplicate(abbrs,words));
		for(int i=0; i<dict.size(); ++i)
			vs[i]=words[dict[i]];
		return vs;
	}
};
